/*
CCP 3.2
How would you design a stack which, in addition to push and pop, 
also has a function min which returns the minimum element? Push, 
pop and min should all operate in O(1) time.

*/
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <map>
#include <list>
#include <algorithm>
#include <functional>
#include <unordered_map>
//#include <tr1/thread>
using namespace std;

template<class T>
class MinStack
{
private:
	stack<T> elemStk;
	stack<T> minStk;
public:
	void push(const T& x)
	{
		if(minStk.empty() || x < minStk.top())
			minStk.push(x);
		elemStk.push(x);
	}
	void pop()
	{
		//assert(!elemStk.empty())
		if(minStk.top() == elemStk.top())
			minStk.pop();
		elemStk.pop();
	}
	int GetMin()
	{
		return minStk.top();
	}
};

int main(int argc, char const *argv[])
{
	/* code */
	MinStack<int> stk;
	stk.push(10);
	stk.push(2);
	stk.push(-1);
	stk.push(5);
	cout<<stk.GetMin()<<endl;
	stk.pop();
	stk.pop();
	cout<<stk.GetMin()<<endl;
	return 0;
}